Chứng minh định lý gồm hai phần: đầu tiên chứng minh sự tồn tại của q và r, thứ hai, chứng minh tính duy nhất của q và r.

Sự tồn tại

Xét tập hợp

S = { a − n d : n ∈ Z } {\displaystyle S=\left\{a-nd:n\in \mathbb {Z} \right\}}

Ta khẳng định rằng S chứa ít nhất một số nguyên không âm. Có hai trường hợp như sau.

• Nếu d < 0, thì −d > 0, và theo tính chất Archimede, có một số nguyên n sao cho (−d)n ≥ −a, nghĩa là a − dn ≥ 0.
• Nếu d > 0, thì cũng theo tính chất Archimede, có một số nguyên n sao cho dn ≥ −a, nghĩa là a − d(−n) = a + dn ≥ 0.

Như vậy S chứa ít nhất một số nguyên không âm. Theo nguyên lý sắp thứ tự tốt, trong S có một số nguyên không âm nhỏ nhất, ta gọi số ấy là r. Đặt q = (a − r)/d, thì q và r là các số nguyên và a = qd + r.

Ta còn phải chỉ ra rằng 0 ≤ r < |d|. Tính không âm của r là rõ ràng theo cách chọn r. Ta sẽ chứng tỏ dấu bất đẳng thức thứ hai.

Giả sử nguợc lại r ≥ |d|. Vì d ≠ 0, r > 0, nên d > 0 hoặc d < 0.

• Nếu d > 0, thì r ≥ d suy ra a-qd ≥ d. Từ đó a-qd-d ≥0, lại dẫn tới a-(q+1)d ≥ 0. Do đó, nếu đặt r’='a-(q+1)d thì r’ thuộc S và r’=a-(q+1)d=r-d <r, điều này mâu thuẫn với tính chất r là phần tử không âm nhỏ nhất của S.
• Nếu d<0 thì r ≥ -d do đó a-qd ≥ -d. Từ đó suy ra rằng a-qd+d ≥0, tiếp tục suy ra r’= a-(q-1)d ≥ 0. Do đó, r’ thuộc S và, vì r’=r+d với d < 0 ta cór’= a-(q-1)d<r, mâu thuẫn với giả thiết r là số nguyên không âm nhỏ nhất trong S.

Như vậy ta đã chứng minh sự tồn tại của q và r.

Tính duy nhất

Giả sử rằng tồn tại q, q' , r, r' với 0 ≤ r, r' < |d| sao cho a = dq + r và a = dq' + r' . Không mất tính tổng quát giả sử q ≤ q' .

Từ hai đẳng thức trên ta có: d(q' - q) = (r - r' ).

Nếu d > 0 thì r' ≤ r và r < d ≤ d+r' , và như vậy (r-r' ) < d. còn nếu d < 0 thì r ≤ r' và r' < -d ≤ -d+r, và do đó -(r- r' ) < -d. Trong cả hai trường hợp ta có |r- r' | < |d|.

Mặt khác đẳng thức d(q' - q) = (r - r' ) chứng tỏ rằng |d| chia hết |r- r' |; do đó |d| ≤ |r- 'r' | hoặc |r- r' |=0. Nhưng vì |r-r' | < |d|, nên chỉ có thể r=r' .Thay vào đẳng thức d(q' - q) = (r - r' ) ta có dq = dq' và vì d khác 0, nên q = q' . Tính duy nhất đã được chứng minh.